package com.leo.basic.chapter03;

import java.util.Random;

/**
 * 跳表
 * @author xuexiaolei
 * @version 2017年11月30日
 */
public class SkipList<E extends Comparable<? super E>> {
    /**
     * 跳表的最大层数，理论上对 2^32-1个元素查询效果优秀
     */
    private final  int MAX_LEVEL = 32;
    /**
     * 当前跳表的有效层
     */
    private int level = 0;
    /**
     * 跳表的头
     */
    private final SkipNode<E> Header = new SkipNode<>(MAX_LEVEL, null);
    private final Random random = new Random();
    private final double E = Math.E;

    /**
     * 跳表是否包含某值
     * @param val
     * @return
     */
    public boolean contains(E val){
        SkipNode<E> cur = Header;
        for (int i = level; i >=0 ; i--) {
            while (cur.next[i]!=null && cur.next[i].val.compareTo(val)<0){
                cur = cur.next[i];
            }
            if (cur.next[i].val.compareTo(val) == 0){
                return true;
            }
        }
        return false;
    }

    /**
     * 插入值
     * @param val
     */
    public void insert(E val){
        SkipNode<E> cur = Header;
        //找到各个层的前继节点
        SkipNode<E>[] predecessors = new SkipNode[MAX_LEVEL];
        for (int i = level; i >= 0; i--) {
            cur = Header;
            while (cur.next[i]!=null && cur.next[i].val.compareTo(val)<0){
                cur = cur.next[i];
            }
            predecessors[i] = cur;
        }

        cur = cur.next[0];
        int nextLevel = randomLevel();
        //如果待插入的节点位置为空 或者 与node节点位置的值不同，则将新节点插入到跳表中
        if (cur ==null || !cur.val.equals(val)){
            //如果新增一层则处理一下
            if (nextLevel > level){
                predecessors[nextLevel] = Header;
                level = nextLevel;
            }
            SkipNode<E> node = new SkipNode<E>(MAX_LEVEL, val);
            for (int i = level; i >=0 ; i--) {
                node.next[i] = predecessors[i].next[i];
                predecessors[i].next[i] = node;
            }
        }
    }

    public void delete(E val){
        SkipNode<E> cur = Header;
        //找到各个层的前继节点
        SkipNode<E>[] predecessors = new SkipNode[MAX_LEVEL];
        for (int i = level; i >= 0; i--) {
            cur = Header;
            while (cur.next[i]!=null && cur.next[i].val.compareTo(val)<0){
                cur = cur.next[i];
            }
            predecessors[i] = cur;
        }

        cur = cur.next[0];
        //跳表不包含此节点
        if (!cur.val.equals(val)) return;
        for (int i = level; i >=0 ; i--) {
            if (!predecessors[i].next[i].val.equals(val)){
                continue;
            }
            predecessors[i].next[i]=cur.next[i];
        }

        //如果删除元素val后level层元素数目为0，层数减少一层
        if (level>0 && Header.next[level]==null){
            level--;
        }
    }

    /**
     * 输出跳表中的元素
     */
    public String toString() {
        StringBuilder sb = new StringBuilder();
        SkipNode<E> cur = Header.next[0];
        sb.append("{");
        while (cur.next[0] != null) {
            sb.append(cur.val);
            sb.append(",");
            cur = cur.next[0];
        }
        sb.append(cur.val);
        sb.append("}");
        return sb.toString();
    }

    /**
     * 随机决定来是否新增加一层
     * @return
     */
    private int randomLevel() {
        double ins = random.nextDouble();
        int nextLevel = level;
        if (ins > E && nextLevel<MAX_LEVEL){
            nextLevel++;
        }
        return nextLevel;
    }

    /**
     * 跳表的节点
     * @param <E>
     */
    class SkipNode<E extends Comparable<? super E>>{
        /**
         * 存储的值
         */
        public E val;
        /**
         * 节点指向第i层节点next[i]
         */
        public SkipNode<E>[] next;

        public SkipNode(int MAX_LEVEL, E val) {
            this.val = val;
            this.next = new SkipNode[MAX_LEVEL];
        }
    }
}
